/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25228
 * Date: 2024-08-11
 * Time: 14:25
 */
class Solution4 {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if(root==null){
            return levelOrder;
        }
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.offer(root);
        while(!queue1.isEmpty()){
            List<Integer> level = new ArrayList<Integer>();
            while(!queue1.isEmpty()){
                TreeNode cur=queue1.poll();
                level.add(cur.val);
                if(cur.left!=null){
                    queue2.offer(cur.left);
                }
                if(cur.right!=null){
                    queue2.offer(cur.right);
                }
            }
            levelOrder.add(0,level);
            Queue<TreeNode> tmp = queue1;
            queue1=queue2;
            queue2=tmp;
            queue2.clear();
        }
        return levelOrder;
    }
}
